home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1997 July / EnigmA AMIGA RUN 20 (1997)(G.R. Edizioni)(IT)[!][issue 1997-07 & 08][EAR-CD IV].iso / earcd / dev / lang / bprolog.lha / Tools / setutl.pl < prev   
Text File  |  1996-06-08  |  9KB  |  292 lines
  1.  
  2. %   File   : SETUTL.PL
  3. %   Author : Lawrence Byrd + R.A.O'Keefe
  4. %   Updated: 19 July 1984
  5. %   Purpose: Set manipulation utilities
  6.  
  7. %   Sets are represented as lists with no repeated elements.
  8. %   An ordered representation could be much more efficient, but
  9. %   these routines were designed before sort/2 entered the language.
  10.  
  11. /*
  12. :- public
  13.     add_element/3,        %  Elem x Set -> Set
  14.     del_element/3,        %  Elem x Set -> Set
  15.     disjoint/1,        %  List ->
  16.     disjoint/2,        %  Set x Set ->
  17.     intersect/2,        %  Set x Set ->
  18.     intersect/3,        %  Set x Set -> Set
  19. %    length/2,        %  List -> Integer
  20.     listtoset/2,        %  List -> Set
  21.     member/2,        %  Elem <- Set
  22.     memberchk/2,        %  Elem x Set ->
  23.     nonmember/2,        %  Elem x Set ->
  24.     pairfrom/4,        %  Set -> Elem x Elem x Set
  25.     select/3,        %  Elem <- Set -> Set
  26.     seteq/2,        %  Set x Set ->
  27.     subset/2,        %  Set x Set ->
  28.     subtract/3,        %  Set x Set -> Set
  29.     symdiff/3,        %  Set x Set -> Set
  30.     union/3.        %  Set x Set -> Set
  31.  
  32. */
  33.  
  34. :- mode
  35. %    length(+, -),
  36. %        length(+, +, -),
  37.     member(?, ?),
  38.     memberchk(+, +),
  39.     nonmember(+, +),
  40.     pairfrom(?, ?, ?, ?),
  41.     select(?, ?, ?),
  42.     add_element(+, +, -),
  43.     del_element(+, +, -),
  44.     disjoint(+),
  45.     disjoint(+, +),
  46.     intersect(+, +),
  47.     subset(+, +),
  48.     seteq(+, +),
  49.     listtoset(+, ?),
  50.     intersect(+, +, ?),
  51.     subtract(+, +, ?),
  52.     symdiff(+, +, ?),
  53.         symdiff(+, +, ?, ?),
  54.     union(+, +, ?).
  55.  
  56. /*  length(List, Length) is true when Length is the number of elements
  57.     in List.  The definition here is correct, but length is actually in
  58.     the Prolog system.  Note that this comment is unclosed!
  59.  
  60. length(List, Length) :-
  61.     length(List, 0, Length).
  62.  
  63.     length([], Length, Length).
  64.     length([_|Tail], SoFar, Length) :-
  65.         Count is SoFar+1,
  66.         length(Tail, Count, Length).
  67.  
  68. /* end of comment */
  69.  
  70. %   member(?Element, ?Set)
  71. %   is true when Set is a list, and Element occurs in it.  It may be used
  72. %   to test for an element or to enumerate all the elements by backtracking.
  73. %   Indeed, it may be used to generate the Set!
  74.  
  75. member(Element, [Element|_]).
  76. member(Element, [_|Rest]) :-
  77.     member(Element, Rest).
  78.  
  79.  
  80.  
  81. %   memberchk(+Element, +Set)
  82. %   means the same thing, but may only be used to test whether a known
  83. %   Element occurs in a known Set.  In return for this limited use, it
  84. %   is more efficient when it is applicable.
  85.  
  86. memberchk(Element, [Element|_]) :- !.
  87. memberchk(Element, [_|Rest]) :-
  88.     memberchk(Element, Rest).
  89.  
  90. %   nonmember(+Element, +Set)
  91. %   means that Element does not occur in Set.  It does not make sense
  92. %   to instantiate Element in any way, as there are infinitely many
  93. %   terms which do not occur in any given set.  That being so, it is
  94. %   sensible to test for membership using == rather than =.  So
  95. %   nonmember(X, S) is not quite the same as \+member(X, S).
  96.  
  97. nonmember(_, []).
  98. nonmember(X, [H|T]) :-
  99.     X \== H,
  100.     nonmember(X, T).
  101.  
  102.  
  103.  
  104. %   add_element(Elem, Set1, Set2)
  105. %   is true when Set1 and Set2 are sets represented as unordered lists,
  106. %   and Set2 = Set1 U {Elem}.  It may only be used to calculate Set2
  107. %   given Elem and Set1.  However, if Set1 is a list with a variable at
  108. %   the end, it may still be used, and will add new elements at the end.
  109.  
  110. add_element(Elem, Set, Set) :-
  111.     memberchk(Elem, Set),
  112.     !.
  113. add_element(Elem, Set, [Elem|Set]).
  114.  
  115. %   del_element(Elem, Set1, Set2)
  116. %   is true when Set1 and Set2 are sets represented as unordered lists,
  117. %   and Set2 = Set1 \ {Elem}.  It may only be used to calculate Set2
  118. %   given Elem and Set1.  If Set1 does not contain Elem, Set2 and Set1
  119. %   will be equal.  I wanted to call this predicate 'delete', but other
  120. %   Prologs have used that for 'select'.  If Set1 is not an unordered
  121. %   set, but contains more than one copy of Elem, only the first will
  122. %   be removed.
  123.  
  124. del_element(Elem, [Elem|Set2], Set2) :- !.
  125. del_element(Elem, [X|Set1], [X|Set2]) :- !,
  126.     del_element(Elem, Set1, Set2).
  127. del_element(_, [], []).
  128.  
  129. %   disjoint(+Set)
  130. %   is true when Set is a list that contains no repeated elements.
  131. %   disjoint/1 and disjoint/2 used to be defined using \+, but for
  132. %   speed (as the Dec-10 compiler does not understand \+), this is
  133. %   no longer so.  Sorry 'bout the !,fails, the price of speed.
  134.  
  135. disjoint([Head|Tail]) :-
  136.     memberchk(Head, Tail),
  137.     !, fail.
  138. disjoint([_|Tail]) :- !,
  139.     disjoint(Tail).
  140. disjoint([]).
  141.  
  142. %   disjoint(+Set1, +Set2)
  143. %   is true when the two given sets have no elements in common.
  144. %   It is the opposite of intersect/2.
  145.  
  146. disjoint(Set1, Set2) :-
  147.     member(Element, Set1),
  148.     memberchk(Element, Set2),
  149.     !, fail.
  150. disjoint(_, _).
  151.  
  152. %   select(?Element, ?Set, ?Residue)
  153. %   is true when Set is a list, Element occurs in Set, and Residue is
  154. %   everything in Set except Element (things stay in the same order).
  155.  
  156. select(Element, [Element|Rest], Rest).
  157. select(Element, [Head|Tail], [Head|Rest]) :-
  158.     select(Element, Tail, Rest).
  159.  
  160. %   pairfrom(?Set, ?Element1, ?Element2, ?Residue)
  161. %   is true when Set is a list, Element1 occurs in list, Element2
  162. %   occurs in list after Element1, and Residue is everything in Set
  163. %   bar the two Elements.  The point of this thing is to select
  164. %   pairs of elements from a set without selecting the same pair
  165. %   twice in different orders.
  166.  
  167. pairfrom([Element1|Set], Element1, Element2, Residue) :-
  168.     select(Element2, Set, Residue).
  169. pairfrom([Head|Tail], Element1, Element2, [Head|Rest]) :-
  170.     pairfrom(Tail, Element1, Element2, Rest).
  171.  
  172.  
  173.  
  174. %   intersect(Set1, Set2)
  175. %   is true when the two sets have a member in common.  It assumes
  176. %   that both sets are known, and that you don't care which element
  177. %   it is that they share.
  178.  
  179. intersect(Set1, Set2) :-
  180.     member(Element, Set1),        %  generates Elements from Set1
  181.     memberchk(Element, Set2),    %  tests them against Set2
  182.     !.                %  if it succeeds once, is enough.
  183.  
  184.  
  185.  
  186. %   subset(+Set1, +Set2)
  187. %   is true when each member of Set1 occurs in Set2.
  188. %   It can only be used to test two given sets; it cannot be used
  189. %   to generate subsets.  At the moment there is NO predicate for
  190. %   generating subsets, but select/3 takes you part-way.
  191.  
  192. subset([], _).
  193. subset([Element|Residue], Set) :-
  194.     memberchk(Element, Set), !,
  195.     subset(Residue, Set).
  196.  
  197.  
  198.  
  199. %   seteq(+Set1, +Set2)
  200. %   is true when each Set is a subset of the other.  There are two
  201. %   ways of doing this.  One is commented out.
  202.  
  203. seteq(Set1, Set2) :-
  204.     subset(Set1, Set2),
  205.     subset(Set2, Set1).
  206. %    sort(Set1, Ord1),
  207. %    sort(Set2, Ord2),
  208. %    Ord1 == Ord2.
  209.  
  210.  
  211.  
  212. %   listtoset(+List, ?Set)
  213. %   is true when List and Set are lists, and Set has the same elements
  214. %   as List in the same order, except that it contains no duplicates.
  215. %   The two are thus equal considered as sets.  If you really want to
  216. %   convert a list to a set, list_to_ord_set is faster, but this way
  217. %   preserves as much of the original ordering as possible.
  218.  
  219. listtoset([], []).
  220. listtoset([Head|Tail], Set) :-
  221.     memberchk(Head, Tail), !,
  222.     listtoset(Tail, Set).
  223. listtoset([Head|Tail], [Head|Set]) :-
  224.     listtoset(Tail, Set).
  225.  
  226. %   intersect(+Set1, +Set2, ?Intersection)
  227. %   is true when Intersection is the intersection of Set1 and Set2,
  228. %   *taken in a particular order*.  In fact it is precisely the
  229. %   elements of Set1 taken in that order, with elements not in Set2
  230. %   deleted.  If Set1 contains duplicates, so may Intersection.
  231. %   This routine is due to Peter Ross and avoids the problem that
  232. %   in the (otherwise) obvious definition,
  233. %   ?- intersection([a,b,c],[a,b,c],[c]) will succeed.
  234.  
  235. intersect([], _, []).
  236.  
  237. intersect([Element|Residue], Set, Result) :-
  238.     member(Element, Set),        % Need not be "memberchk" because of
  239.     !,                % the cut here
  240.     Result = [Element|Intersection],
  241.     intersect(Residue, Set, Intersection).
  242.  
  243. intersect([_|Rest], Set, Intersection) :-
  244.     intersect(Rest, Set, Intersection).
  245.  
  246. %   subtract(+Set1, +Set2, ?Difference)
  247. %   is like intersect, but this time it is the elements of Set1 which
  248. %   *are* in Set2 that are deleted.
  249.  
  250. subtract([], _, []).
  251. subtract([Element|Residue], Set, Difference) :-
  252.     memberchk(Element, Set), !,
  253.     subtract(Residue, Set, Difference).
  254. subtract([Element|Residue], Set, [Element|Difference]) :-
  255.     subtract(Residue, Set, Difference).
  256.  
  257.  
  258.  
  259. %   symdiff(+Set1, +Set2, ?Diff)
  260. %   is true when Diff is the symmetric difference of Set1 and Set2,
  261. %   that is, if each element of Union occurs in one of Set1 and Set2,
  262. %   but not both.  The construction method is such that the answer
  263. %   will contain no duplicates even if the Sets do.
  264.  
  265. symdiff(Set1, Set2, Diff) :-
  266.     symdiff(Set1, Set2, Diff, Mid),
  267.     symdiff(Set2, Set1, Mid, []).
  268.  
  269. symdiff([Elem|Rest], Avoid, Diff, Tail) :-
  270.     memberchk(Elem, Avoid), !,
  271.     symdiff(Rest, Avoid, Diff, Tail).
  272. symdiff([Elem|Rest], Avoid, [Elem|Diff], Tail) :- !,
  273.     symdiff(Rest, [Elem|Avoid], Diff, Tail).
  274. symdiff([], _, Tail, Tail).
  275.  
  276.  
  277.  
  278. %   union(+Set1, +Set2, ?Union)
  279. %   is true when subtract(Set1,Set2,Diff) and append(Diff,Set2,Union),
  280. %   that is, when Union is the elements of Set1 that do not occur in
  281. %   Set2, followed by all the elements of Set2.
  282.  
  283. union([], Set2, Set2).
  284. union([Element|Residue], Set, Union) :-
  285.     memberchk(Element, Set), !,
  286.     union(Residue, Set, Union).
  287. union([Element|Residue], Set, [Element|Union]) :-
  288.     union(Residue, Set, Union).
  289.  
  290.  
  291.  
  292.